МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
АЛГОРИТМИ ДЛЯ ВИКОНАННЯ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 1 З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” Затверджено на засiданнi кафедри “Захист інформації”, протокол № від 2008 р. Львів – 2008 Алгоритми для виконання операцій з довгими числами: Методичні вказівки до лабораторної роботи №1 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с. Укладачі: А.Е.Лагун, к.т.н., доцент В.М.Іванюк, асистент Відповідальний за випуск: І.Я. Тишик, старший викладач. Рецензент: В.В.Максимович, д.т.н., професор. Мета роботи - вивчити способи представлення та алгоритми для виконання операцій введення-виведення, порівняння, підсумовування, віднімання довгих чисел та навчитися розробляти програмне забезпечення для реалізації перерахованих алгоритмів на комп’ютері. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ 1.1. Розміщення в пам’яті комп’ютера довгих чисел та аналіз типів даних для виконання арифметичних операцій з ними. Арифметичні дії, що виконуються комп’ютером в обмеженій кількості розрядів не завжди дозволяють одержати точний результат. Також існують обмеження на розмір (величину) чисел, з якими можна працювати. Прикладом може бути виконання дій з дуже великими числами, наприклад 30! = 265252859812191058636308480000000. В таких випадках необхідно певним чином представити числа в машині та точно виконати арифметичні операції з ними. Число 30! можна представити у вигляді: 30!=2•(104)8+6525•(104)7+2859• (104)+8121•(104)5+9105•(104)4+8636•(104)3+3084•(104)2+8000•(104)1+0000•(104)0. Таке представлення записується у вигляді масиву (таблиця 1). Можна вважати, що наведене "довге" число представлене в 10000–10 системі числення, а "цифрами" числа є чотиризначні числа. Таблиця 1. Номер элементу в масиві А 0 1 2 3 4 5 6 7 8 9  Значення 9 0 8000 3084 8636 9105 8121 2859 6525 2  Числа, для представлення яких в стандартних комп’ютерних типах даних не вистачає кількості двійкових розрядів, називаються довгими, а алгоритми реалізації арифметичних операцій з довгими числами – довгою арифметикою. Алгоритми роботи з довгими числами залежать від представлення користувачем цих чисел в комп’ютері. Довге число можна записати, наприклад, за допомогою масиву десяткових цифр. Кількість елементів такого масиву дорівнює кількості значущих цифр в довгому числі. Проте, якщо реалізувати арифметичні операції з цим числом, то розмір масиву має бути достатнім, щоб розмістити в ньому і результат, наприклад множення. В десятковій та інших позиційних системах числення декілька записаних поруч цифр формують число. Множина можливих значень кожної цифри обмежена, проте за рахунок позиційної ваги, яка залежить від положення цифри, за допомогою короткого запису представляються достатньо великі числа. Цей алгоритм можна використати для побудови довгих чисел. Якщо взяти масив звичайних цілих і вважати його позиційним записом довгого числа у системі числення з деякою основою, наприклад B, то кожен елемент масиву набуває значення з діапазону від 0 до В-1, а N таких елементів дозволять представити числа від 0 до ВN-1. Наступним кроком алгоритму є виділення місця для запису довгого числа. В першу чергу потрібно визначитися із типом запису довгого числа в масив, а саме як записати довге число в масив: з початку чи з кінця масиву, з початку чи з кінця числа. Наприклад, для N=6, B=10 розмістимо число 2000. Можливі чотири варіанти (таблиця 2): Таблиця 2. № варіанту Тип запису  1   2 0 0 0  2   0 0 0 ...